package src.算法.归并排序;

public class Merge {
    private static  Comparable[] assist;

    public static void sort(Comparable[] a){
        // 1.初始化辅助数组assist
        assist = new Comparable[a.length];
        // 2.定义lo、hi变量，分别记录组中最小值的索引和最大值的索引
        int lo = 0;
        int hi = a.length-1;
        // 3.调用重载后的sort方法，从索引lo到hi排序
        split(a,lo,hi);
    }
    private static void split(Comparable[] a,int lo,int hi){
        // 将一个数组拆分为2个
        // 安全性校验
        if(hi<=lo){
            return;
        }
        // 对lo到hi之间的数据进行分为2组
        int mid = lo+(hi-lo)/2;
        // 分别对各组的数据进行排序
        split(a,lo,mid);
        split(a,mid+1,hi);
        // 再将两组数据结合到一起
        merge(a,lo,mid,hi);
    }
    private static void merge(Comparable[] a,int lo ,int mid ,int hi){
        // 定义三个指针
        int i = lo;
        int p1 = lo; // 左数组
        int p2 = mid+1; // 右数组
        // 遍历移动p1和p2指针，比较对应索引值，比较小的那个，放入辅助数组中
        while (p1<=mid && p2<=hi){
            if(less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }else {
                assist[i++] = a[p2++];
            }
        }
        // 遍历，如果p1指针没有走完，则顺序移动p1指针插入辅助数组，反之如此
        while (p1<=mid){
            assist[i++] = a[p1++];
        }
        while (p2<=hi){
            assist[i++] = a[p2++];
        }
        // 将辅助数组的数据拷贝到原数组
        for (int j = lo; j <= hi; j++) {
            a[j] = assist[j];
        }
    }
    // 比较前一个元素是否小于后一个元素
    private static boolean less(Comparable a,Comparable b){
        int result = a.compareTo(b);
        return result<0;
    }
    // 数组元素i和j交换位置
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
